// https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
// 215. Kth largest element in an array
// Given an integer array nums and an integer k, return the kth largest element
// in the array
// Note that it is the kth largest element in the sorted order, not the kth distinct
// element

function findKthLargest(nums: number[], k: number): number {
    for (let i = 0; i < k; i++) {
        swim(i);
    }

    for (let i = k; i < nums.length; i++) {
        if (nums[i] > nums[0]) {
            swap(i, 0);
            sink(0, k - 1);
        }
    }

    return nums[0];

    function priorThan(a: number, b: number): boolean {
        return nums[a] < nums[b];
    }

    function pid(i: number): number {
        return Math.floor((i - 1) / 2);
    }

    function swim(i: number) {
        while (i > 0 && priorThan(i, pid(i))) {
            swap(i, pid(i));
            i = pid(i);
        }
    }

    function sink(i: number, n: number) {
        while (2 * i + 1 <= n) {
            let j = 2 * i + 1;
            if (j + 1 <= n && priorThan(j + 1, j)) {
                j++;
            }
            if (priorThan(i, j)) break;
            swap(i, j);
            i = j;
        }
    }

    function swap(i: number, j: number): void {
        [nums[j], nums[i]] = [nums[i], nums[j]];
    }
}

findKthLargest([7, 6, 5, 4, 3, 2, 1], 5);
